A great advantage of packet and cell switched networks, like ATM is efficiency. Most traffic in a network is bursty in nature, because most traffic sources like people surfing on the web (i.e. the Internet) or talking to the phone have idle or almost idle periods. When the burstiness is combined with statistical discovery that bursts unlikely occur coincidentally, obviously there is some new efficiency available. We can take advantage of this efficiency with statistical multiplexing, which means having transfer capacity much smaller than the total sum of the peak capacity consumption of users. The term statistical multiplexing gain is used to denote the factor of the efficiency achieved.
The reverse of this efficiency is uncertainty. By providing a capacity less than the sum of peak consumption of users, we always take a statistical risk of congestion. The less capacity we provide, the more likely the offered traffic momentarily exceeds the offered capacity. To prevent the loss of data during rush means to store excess packets into a buffer for a moment. At this point, usually two questions arises: is the buffer large enough to keep the packet loss low enough or is the waiting time of packets in the buffer too long for users? We can think of this also as a kind of intuitive definition of quality of service (QoS). From users' point of view QoS is defined in terms of transfer delay, delay variation and proportional to lost data to send data.
The core idea of the ATM is achieving a combination of these two matters: efficiency and quality of service. With a time-division based system one could have guaranteed QoS for different bandwidth requirements but remarkable loss of efficiency would have been caused by allocation of resources according to absolute peak consumption. Unfortunately, carrying out this promising combination of quality and efficiency has proven much more difficult the early visionaries of ATM thought.
In ATM the functional entity which has responsibility for determining whether there are enough resources for a new connection is commonly named as connection admission control (CAC). The limited resources are bandwidth and buffer space as in the case of any packet switched network. In specifications, it is not detailed how the determination of resource availability should be done. It is up to manufacturer.
In general, connection admission control methods are divided into two groups:
preventive CACs which determine the current usage of resources using traffic descriptor parameters of ongoing connections, announced by users at connection request, and
measurement-based CACs (MBACS) which measure the current use of resources.
Because this application focuses on ATM (Asynchronous Transmission Mode) networks as an example of packet data networks, in the following the traffic classification and QoS definitions used in connection with ATM are briefly introduced for subsequent better understanding.
In an ATM network a traffic contract between a user and the network consists of QoS parameters on one hand and connection traffic description on the other hand. The latter one, in turn, comprises a source traffic description, a CDVT (cell delay variation tolerance) parameter and a conformance definition.
The end system, i.e. the network, announces the end-to-end QoS requirements of a new connection in terms of QoS parameters. The QoS parameters are maximum Cell Transfer Delay (maxCTD), peak-to-peak Cell Delay Variation (CDV) and Cell Loss Ratio (CLR). The maxCTD is defined so that the fraction of the cells violating maxCTD, that is, the fraction of the cells delivered late, is equal to or less than the CLR. The relationship between the maxCTD and CDV is clear: CDV is the difference between maxCDV and the minimum possible transfer delay.
Source traffic descriptor consists of traffic parameters describing the behavior of the traffic source of the end system. Four traffic parameters have been defined: Peak Cell Rate (PCR), Sustainable Cell Rate (SCR), Maximum Burst Size (MBS) and Minimum Cell Rate (MCR). Note that PCR, SCR are announced as cells per second whereas MBS is announced in cells.
The CDVT part consist of a single Cell Delay Variation Tolerance (CDVT) parameter. The end system either gives a value for CDVT or accepts the value suggested by the network. The existence of the CDVT value is dictated by the practice, because ATM layer does not work as an ideal transportation medium. In theory, connections having PCR value defined are not allowed to send cells closer to each other than T=1/PCR and therefore the switch could assume that the PCR is the absolute peak rate of the connection. In practice, the ATM layer is not able to transport given cells immediately, because there is a variable transmission delay due to insertion of maintenance cells and an overhead of lower transportation protocol, for example, SDH. As a result, the cell intervals at the user-network interface (UNI) are not constant any more, because some cells arrive closer to each other as clumps or clusters, respectively.
In such a situation of cells arriving in clumps or clusters, one can observe the fluctuating transmission delay with a minimum of dmin and a maximum of dmax. In this case, where the user application is sending at peak rate with interarrival times of T=1/PCR, the cell stream at the ATM link can be described with GCRA(T,CDVT) where CDVT=dmax−dmin. (Note that GCRA denotes a so-called Generic Cell rate algorithm.)
In general, the conformance definitions of the connections in ATM are based on the GCRA algorithm. The number of GCRA leaky buckets and the set of traffic parameters used depend on the service category. Moreover, in certain cases, the end systems are allowed to send more traffic than judged conformant by the GCRA by setting a special Cell Loss Priority (CLP) bit in the header of the offending cells. In the case of congestion in the network, these tagged cells are the first ones subject to discarding.
Furthermore, to serve a wide range of communication needs, ATM provides four service categories. In each category, QoS definition, source traffic description and conformance definition is different due to different characteristics of the services.
Constant bit rate (CBR) service with very small CDV and CLR requirements is intended to emulate circuit-switched connections. In addition to CDV and CLR, also maxCTD is defined for a CBR connection. The source traffic descriptor consist of only PCR parameter, and the conformance definition of the connection is defined by GCRA(1/PCR,CDVT). The CBR service is suitable for real-time applications producing almost constant rate traffic.
There are two types of variable bit rate (VBR) services: real-time (rt-VBR) and non-real-time (nrt-VBR) services. With both type of connections, source traffic descriptor consist of PCR, SCR and MBS parameters, where PCR>SCR. The conformance definition of both rt-VBR and nrt-VBR is defined with two leaky buckets, also called dual leaky bucket: GCRA(1/PCR,CDVT) and GCRA(1/SCR,τ+CDVT), where τ=(MBS−1) (1/SCR−1/PCR). The difference between these two services is in the QoS definition. For rt-VBR, all three QoS parameters, maxCTD, CDV and CLR, are defined, whereas for nrt-VBR, only CLR is defined. VBR services are intended for bursty traffic sources having high peak-to-mean rate ratio. Due to two bit rate parameters, PCR and SCR, the network may take advantage of statistical multiplexing. The rt-VBR is naturally intended for applications having real-time requirements.
Unspecified bit rate service (UBR) has been specified for traditional adaptive data services not requiring any QoS guarantees. Internet-like best effort service enables quite a good utilization of free capacity and therefore compensation of low utilization caused by imperfect CAC of other service classes. Possible congestion control is assumed to be a part of higher protocol layers, like TCP. For UBR connections, no QoS parameters are defined. However, the end system must announce PCR parameter of the source traffic descriptor, because ATM networks may optionally perform CAC check for UBR connections.
To provide a rapid access to the continuously changing amount of unused bandwidth, an available bit rate (ABR) service has been defined. A traffic source using ABR connection adjusts its transmission rate according to the feedback sent by the switches along the connection. ATM Forum specifications defines two kinds of feedback methods. First, a switch may control source implicitly by announcing about congestion with congestion indicator bit in either resource management cells or data cells. Second, a switch may control the source explicitly by telling it the share of the available bit rate at which the source is allowed to send. In the traffic contract, no QoS parameters are defined. The traffic source descriptor consists of PCR and minimum cell rate (MCR) parameters, where the MCR denotes the minimum bandwidth the connection needs. Standard GCRA conformance definition is not applied since the conformance depends on the feedback method used.
Implementation of the ABR service efficiently may be hard, as it requires a lot from CAC. In addition, the need for the ABR service may be arguable as far as IP and especially TCP are run over ATM.
Now, returning to the two different types of CAC methods mentioned above, these are briefly compared with each other.
The motivation for developing MBAC has originated from a few essential drawbacks in ATM traffic model;
First, it is difficult for the user to characterize his traffic in advance and because the network polices traffic contract, the user prefers overestimation.
Second, deterministic traffic model based on leaky buckets is easy to police, but traffic flows with rate variations over multiple time scales are not adequately characterized by two leaky buckets which give only the worst-case upper bound leaving a large fraction of potential statistical multiplexing gain unreachable.
Third, as a result, preventive CAC making decision on the basis of only traffic parameters combines the effect of both of these inefficiencies.
In other words, the main objective of MBAC is efficiency.
Users may describe their sources with very conservative parameters, because the resource demand of connections is determined by parameters only when connections are established—later their real resource need is measured.
Since MBAC determines availability of resources for a new connection on the basis of the measured behavior of existing connections, it is possible to achieve high utilization even with overly conservatively specified traffic descriptors.
MBAC also tolerates burst scale external dependencies of sources, unlike preventive CAC methods, which would allow too many connections.
Characteristics of real traffic such as long-range dependence make modeling of traffic very hard and models complex, and therefore reliable analytical evaluation of the performance of preventive algorithms is hard, especially with those taking large buffers into account.
Moreover, the performance of preventive algorithms in terms of utilization is not very easily compared, because results depend on the traffic model used. Therefore it is difficult to avoid simulations and empirical studies even with preventive algorithms.
One fundamental difference between preventive and measurement-based CAC must be understood:
MBAC offers only a predicted, not guaranteed QoS, whereas preventive CAC suppose worst-case traffic in calculations to guarantee QoS. This is due to the fact that MBAC relies only on measurements and because the behavior of sources varies over time, there is no guarantee that an estimate based on current and past measurements holds in future. If a mistaken estimation is made, MBAC is able to adapt to the new situation but this takes some time depending on the system dynamics.
There is also one conceptual difference between preventive CAC and MBAC. The term CAC and most, if not all, preventive CAC methods originate from the broadband ISDN and ATM world, where tight QoS objectives are assumed. Due to the predictive nature of MBAC, many MBAC proposals are of a very general type and intended to serve any packet switched network, like Internet. Th present application is not concerned with this, because the aim of MBAC, achieving high utilization without violating QoS, is very general and common to all packet switching networks that provide QoS guarantees. For ATM as an example, we should choose a MBAC scheme that is able to preserve even quite strict QoS objectives, but it does not preclude us from investigating different schemes, even those intended for IP networks.
Naturally measurements constitute an essential part of any MBAC system. It is therefore considered first, what it is actually possible to measure.
Remember that a switch can be though of as a collection of multiplexers. Cells arrive into the multiplexer according to some arrival process (at a plurality of input terminals) and leave the multiplexer through shared output link (at least one output terminal). Coincident cells are buffered until they are drawn from buffer to be sent forward. In this model, there are the following basic quantities that can be measured:
1. The number of cells arriving at the multiplexer (before buffering)
2. The number of cells leaving the multiplexer (after buffering)
3. The delay experienced by cells.
The delay itself is a useful quantity, but it is to be noticed that there is no cell rate mentioned. This is due to the fact that the arrival rate, as well as utilization, cannot be measured directly but must be calculated as an average over some interval:
The rate of incoming cells can be calculated counting the number of arrived cells during some interval.
The rate of outgoing cells can be calculated similarly.
Utilization is related to rate, because utilization can be calculated as the ratio of the rate of outgoing cells to the maximum link rate.
Cell loss ratio is defined as the ratio of lost cells to arrived cells, where the number of lost cells is calculated as a difference between the number of arrived and departed cells.
It seems that the three listed measurements are able to fulfill most of the measurement needs.
Among recently introduced MBAC methods, the so-called “Qiu's MBAC” has found considerable attention. This MBAC method has been developed by J. Qui and E. Knightlyly and presented by these in the article: “Measurement-Based Admission Control Algorithm with Aggregate Traffic Envelopes”, in: Proceedings of the 10th IEEE ITWDC, Ischia, Italy, September 1998.
However, the rather theoretical approach presented in that paper is not yet perfect in order to be applied to practically existing switch means in packet data networks such as ATM switches.
Namely, having regard to such existing and/or currently used switch means, from implementation point of view, the wide range of delay bound requirements is not the only inconvenient consequence of the existence of several service categories.
Another one is the fact that all service categories must be carried through the same physical interface (i.e. switch means) while simultaneously still conforming QoS requirements of each category.
For example, some basic technologies used to implement service categories in ATM switches are presented herein above.
The basic concept of packet and cell multiplexing is scheduling. Scheduling is considered as a discipline according to which the next cell to be carried by output interface (output terminal) is chosen from a buffer that is always needed to accommodate arrivals of cells.
Whenever the buffer has more than one cell, it is up to the scheduler to choose the next cell to be served.
The cell buffer of a switching unit and/or switch means may be organized in many ways. Although the buffer often physically consists of one shared memory, the cells in the buffer memory are logically arranged into one or more queues.
From theoretical point of view, the scheduler could search and choose the most important cell from the queue but in practice the implementation of any such search algorithm is hard and therefore one usually have as many FIFO queues as needed.
Subsequently, the question arises: how should the FIFO queues be organized and how should the scheduler choose the next queue to be served? Assigning one queue for each connection and serving the queues in round robin fashion would provide fairness among connections, because bursts of one connection would not be able to cause additional delay for other connections. In addition, the service rate of the round robin scheduler should be weighted according to agreed traffic rate of each connection.
However, a weighted round robin scheduler cannot provide statistical multiplexing unless it is able to take advantage of silent periods of any connection to carry bursts of other connections. This in turn complicates the realization of the scheduler.
As a conclusion, per connection queuing sets hard requirements for scheduling discipline as it needs to preserve QoS of connections and still achieve good throughput.
Therefore, a first step of implementation of different service categories in an ATM switch resides in the use of shared static priority queues.
In this scenario, the switch means or switching unit has P static priority queues for each input and/or output, and possibly for each internal transport interface, and the scheduler always serves the queue of the highest priority having cells. Naturally the cells of the highest priority experience the shortest delay. One priority class is usually assigned to one or more service categories.
A wide variety of more sophisticated scheduling disciplines than the static priority, such as the rate-controlled static priority, has been developed. However the static priority implementation, as it is a widely known and used, is far more easy to implement even in large high bit rate systems.
Quite a complete worst-case delay analysis of such (static) priority queues is known from document “Exact Admission Control for Networks with a Bounded Delay Service” by J. Liebeherr, D. Wrege and D. Ferrari, in IEEE/ACM Transactions on Networking, Vol. 4, No. 6, pp. 885–901, 1996.
This document gives equations for theoretical maximum delays in static priority queue systems, assuming the arrival characteristics, i.e. exact arrival constraints are known. However, this document is silent about how these constraints are obtained, for example by measurement, or by other means.
Still further, delay calculations of priority queues are more complicated than in the case of FIFO queues. The delay of the highest priority queue, usually denoted as a priority 1, is the only exception since its delay is same as with FIFO queue. The service rate of lower priority queues is always determined by workload of higher priority queues.
Therefore one of the requirements of the Qiu's MBAC method mentioned later, i.e. the minimum service rate of the queue, cannot be fulfilled, so that Qiu's MBAC method can not be applied to such static priority queues.
Summing up, current MBAC methods, such as the Qiu MBAC method, proposed in the literature are still immature, and not ready-to-use as an all-purpose algorithm in pratical situations. Generally, problems are related to difficult tuning of measurement and estimation parameters.
From the point of view of the ATM technology as an example technology of particular interest for packet data networks, current MBAC proposals proved to have a great number of deficiencies.
Firstly, most proposals assume a simplified switching model consisting of a simple cell multiplexer (switch). In reality, however, the complex traffic model of ATM makes the hardware implementation of switches complicated and for example a static priority queue system cannot be reduced to a collection of multiplexers with constant service rates.
Secondly, real-time services have tight delay variation and cell loss requirements which most MBAC methods are not designed to deal with.
Thirdly, virtual paths complicate admission control, because both VPC (Virtual Path Connection) conformance checks and VPC end point admission control need different admission control checks than normal VCC (Virtual Channel Connection) or VPC cross connections.
Moreover, MBAC methods impose quite a hard processing load on a control device for switch means such as ATM switches when implemented to such commercially available switches means, which up to now has prevented their practical implementation in connection with existing switch means, since a processor overload and even “collapse” of the performance would have to be expected.